import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class SolutionLCP13 {
    public int minimalSteps(String[] maze) {
        List<int[]> ms=new ArrayList<>();
        List<int[]> os=new ArrayList<>();
        int[] start=new int[2];
        int[] end=new int[2];
        int m=maze.length,n=maze[0].length();
        char[][] map=new char[m][n];
        for (int i=0;i<m;i++){
            map[i]=maze[i].toCharArray();
            for (int j=0;j<n;j++){
                if (map[i][j]=='S'){
                    start[0]=i;
                    start[1]=j;
                }else if (map[i][j]=='T'){
                    end[0]=i;
                    end[1]=j;
                }else if (map[i][j]=='M'){
                    ms.add(new int[]{i,j});
                }else if (map[i][j]=='O'){
                    os.add(new int[]{i,j});
                }
            }
        }
        List<int[]> all=new ArrayList<>();
        all.add(start);
        for (int[] ints : ms) {
            all.add(ints);
        }
        int r=all.size();
        for (int[] ints : os){
            all.add(ints);
        }
        all.add(end);
        int[][] dis=new int[all.size()][all.size()];
        for (int i=0;i<all.size();i++){
            Arrays.fill(dis[i],-1);
            int[][] target=find(map,all.get(i));
            for (int j=0;j<all.size();j++){
                dis[i][j]=target[all.get(j)[0]][all.get(j)[1]];
            }
        }
        int[][] f=new int[all.size()][1<<ms.size()];
        for (int[] ints : f) {
            Arrays.fill(ints,Integer.MAX_VALUE/2);
        }
        f[0][0]=0;
        return dfs(all.size()-1,(1<<ms.size())-1,f,r,dis);
    }

    private int dfs(int m, int k, int[][] f,int r,int[][] dis) {
        if (f[m][k]!=Integer.MAX_VALUE/2){
            return f[m][k];
        }
        if (k==0){
            f[m][k]=dis[0][m];
            return f[m][k];
        }
        if (m>0 && m<r){
            int p=k&(~(1<<(m-1)));
            for (int i=r;i<f.length-1;i++){
                if (dis[i][m]!=-1){
                    int d = dfs(i,p,f,r,dis);
                    if (d!=-1) {
                        f[m][k]=Math.min(f[m][k], d+dis[i][m]);
                    }
                }
            }
        }else {
            for (int i=1;i<r;i++) {
                if ((k&(1<<(i-1)))>0 && dis[m][i]!=-1) {
                    int d = dfs(i,k,f,r,dis);
                    if (d!=-1) {
                        f[m][k]=Math.min(f[m][k], d+dis[i][m]);
                    }
                }
            }
        }
        if (f[m][k]==Integer.MAX_VALUE/2){
            f[m][k]=-1;
        }
        return f[m][k];
    }

    private int[][] find(char[][] map, int[] start) {
        int[] dx={1,0,-1,0};
        int[] dy={0,1,0,-1};
        int[][] ans=new int[map.length][map[0].length];
        for (int[] an : ans) {
            Arrays.fill(an,-1);
        }
        ans[start[0]][start[1]]=0;
        Queue<int[]> queue=new LinkedList<>();
        queue.add(new int[]{start[0],start[1],0});
        while (!queue.isEmpty()){
            int[] t=queue.poll();
            for (int i=0;i<4;i++){
                int x=t[0]+dx[i];
                int y=t[1]+dy[i];
                if (valid(x,y,map.length,map[0].length) && map[x][y]!='#' && ans[x][y]==-1){
                    ans[x][y]=t[2]+1;
                    queue.add(new int[]{x,y,t[2]+1});
                }
            }
        }
        return ans;
    }

    private boolean valid(int x, int y, int m, int n) {
        return x>=0 && y>=0 && x<m && y<n;
    }

    public static void main(String[] args) {
        System.out.println(new SolutionLCP13().minimalSteps(new String[]{"MM#", "OO#", "OST", "#M#", "M.M", "MMM", "##O"}));
    }
}
